// builder_prim.cpp: Source for Prim's algorithm adapted for maze generation 
// Written by Victor Luna Freire - victorclf@live.com
// Copyright (c) Victor Luna Freire. All rights reserved.
// Sunday, October 25, 2009 12:15:43 AM

#include "builder_prim.h"

// Construct BuilderPrim of desired width and height.
BuilderPrim::BuilderPrim(int width, int height) : Builder(width, height)
{
	start_process();
}


// Get starting position for maze generation.
Vec2i BuilderPrim::get_start_cell() 
{
	// TODO: finish this! int BuilderPrim::get_start_pos() 
	return Vec2i(random(w), random(h));
}


// Start building maze with adapted Prim's algorithm.
void BuilderPrim::start_process() 
{	
	cellmaze.assign(h, std::string(w, UNTOUCHED));
	
	Vec2i start_cell = get_start_cell();
	cellmaze[start_cell.y][start_cell.x] = ADDED;
	
	std::vector<Vec2i> new_adj_cells = get_adjacent_cells(start_cell);
	adj_cells.clear();
	for(std::vector<Vec2i>::iterator itr = new_adj_cells.begin(); itr != new_adj_cells.end(); ++itr)
		adj_cells.push_back(std::make_pair(start_cell, *itr));
}


// Perform the next step in the build. Returns false if the build is over. Starts the building if it was not started before.
bool BuilderPrim::next_step()
{
	// Make sure the build was started
	if(maze.empty()) start_process();
	
	// Process next adjacent cell (each cell is a step)
	if(!adj_cells.empty()) {
		// Pick random cell adjacent cell from the list.
		std::random_shuffle(adj_cells.begin(), adj_cells.end());
		std::pair<Vec2i, Vec2i> adj_cell_pair = adj_cells.back();
		Vec2i origin_cell = adj_cell_pair.first; //the cell which spawned this adjacent cell
		Vec2i current_cell = adj_cell_pair.second; // the adjacent cell we are processing
		adj_cells.pop_back();
		
		// Carve a passage between a cell and its adjacent.
		carve(current_cell, origin_cell);
		
		// Add this cell's adjacent cells.
		std::vector<Vec2i> new_adj_cells = get_adjacent_cells(current_cell);
		for(std::vector<Vec2i>::iterator itr = new_adj_cells.begin(); itr != new_adj_cells.end(); ++itr)
			if(cellmaze[itr->y][itr->x] == UNTOUCHED) {
				cellmaze[itr->y][itr->x] = FRONTIER;
				adj_cells.push_back(std::make_pair(current_cell, *itr));
			}
		
		// Set this cell as processed.
		cellmaze[current_cell.y][current_cell.x] = ADDED;
		return true;
	}

	return false;	
}

//
//int main() 
//{
//	int w, h;	
//	std::cin >> w >> h;
//	BuilderPrim maze(w, h);
//	maze.all_steps();
//	std::cout << maze;
//	return 0;
//}
